import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/4 10:49
 * @description 翻转链表后半部分，然后同步移动指针
 */
public class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(5, new ListNode(4, new ListNode(2, new ListNode(1))));
        Solution solution = new Solution();
        solution.pairSum(listNode);
    }
    public int pairSum(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode next = slow.next;
        // 断开连接
        slow.next = null;
        ListNode halfReverse = reverse(next);
        int max = 0;
        while (halfReverse != null) {
            max = Math.max(head.val + halfReverse.val, max);
            head = head.next;
            halfReverse = halfReverse.next;
        }
        return max;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
